package offer;

import java.util.Stack;

/**
 * @Author SSK
 * @Date Created in 17:14 2019/8/8
 * @Description 二叉搜索树的第k个结点
 * @Version 1.0
 */
public class T63 {
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }

    }
    TreeNode KthNode(TreeNode pRoot, int k)
    {
         if (pRoot==null) {
             return null;
         }
        Stack<TreeNode> stack = new Stack<TreeNode>();
         stack.push(pRoot);
         while (pRoot.left!=null) {
             stack.push(pRoot.left);
             pRoot = pRoot.left;
         }
         while (!stack.isEmpty()) {
             TreeNode treeNode = stack.pop();
             k--;
             if (k==0) {
                 return treeNode;
             }
             if (treeNode.right!=null) {
                 treeNode = treeNode.right;
                 stack.push(treeNode);
                 while (treeNode.left!=null) {
                     stack.push(treeNode.left);
                     treeNode = treeNode.left;
                 }
             }

         }
         return null;
    }
}
